1. Field of Invention
This invention relates to encoding a digital word and more specifically to a run length limited encoding of a digital word.
2. Description of Related Art
In current digital data communication and digital data storage systems the processes of encoding and decoding are frequently utilized. During the encoding process the input stream of 0""s and 1""s is convert into another stream of 0""s and 1""s. The encoded stream usually contains more bits than the original uncoded stream. For example, encoding process could have data divided into words of 32 bits which are then converted into coded words, each 33 bits long. Such an encoding process is referred to as a rate of 32/33.
In U.S. Pat. No. 5,781,130 (McLaughlin et al.)( a system for encoding a digital word with an M-ary(d,k) code is disclosed. The multilevel coded data for M greater than 2 is a result of an M-ary encoder that produces a run length limited code for multilevel data storage and/or data communications. In U.S. Pat. No. 5,748,119 (Ko) channel encoding and decoding methods are described which use an EFM code with a reduced number of merging bits. An m-bit input word is encoded to an (nxe2x88x92d+1) bit channel word by an encoding table. One or more merge bits are added encoded channel word to form a n-bit channel word. In U.S. Pat. No. 5,604,497 (Sonntag) a method and apparatus is disclosed for increasing the density of run length limited block codes without increasing error propagation. This is accomplished by inserting xe2x80x9cMxe2x80x9d uncoded bytes between each coded byte which increases the coding density.
The goal of encoding is to produce a stream of bits better suited for digital transmission or digital recording. One common objective is to guarantee that the encoded stream can not have more than a predetermined number xe2x80x9cnxe2x80x9d of consecutive zeros. This coding requirement is referred to as (0,n) Run Length Limited (RLL) constraint. During the digital transmission or digital recording, logical 1""s are often modulated as a pulse and logical 0""s are modulated as no pulse. The long runs of consecutive zeros result in long periods with no pulses which make it difficult to perform timing and gain recovery of the transmitted or stored signal. There is another important type of constraint which is commonly referred to as (0,G/I) constraint. Here the encoded stream can not have more than xe2x80x9cGxe2x80x9d consecutive zeros and after the encoded sequence of bits is divided into the odd-number and even-numbered sub sequences then neither of these sub sequences can have more than xe2x80x9cIxe2x80x9d consecutive zeros. The need for utilizing the (0,G/I) constraint streams from the use of Viterbi detection. Therefore, it is desirable to design an encoder which has a high rate, e.g. 32/33 or 64/65, has low implementation complexity and which satisifies a (0,G/I) RLL constraints with small values of G and I.
In the present invention a method for encoding an input digital word is shown that results in an output digital word that is one bit longer than the input digital word before parity bit is added. The output digital word satisifies a run length limited (RLL) (0,11/11) constraint and a Hamming weight of nine. Having a Hamming weight of xe2x80x9c9xe2x80x9d means that the number of logical ones in a word is at least nine.
As an example, a thirty two bit word can be encoded into a thirty three bit word plus a parity bit. The thirty two bit input word can be defined as IN={in(1), in(2), . . . in(32)} and the thirty three bit output word can be defined as OUT={out(1), out(2), . . . out(33)}. If the input word, IN, satisfies the coding constraints of (0,11/11) and a Hamming weight of at least nine, the input word split in half can be directly transferred to the output word as OUT={IN(LH), out(17), IN(RH)}, where IN(LH)={in(1), in (2), . . . in(16)} is the left half of the input code word, out(17) is the seventeenth bit position of the output code word, and IN(RH)={in(16), in (17), . . . in(32)} is the right half of the input code word. For convenience of demonstration and consistency with programs such as MATLAB the notation in(16:32) will be used instead of {in(16), in(17), . . . in(32)}. The left half of the input word maps directly into the same numbered bit positions in the left half of the output code word, and the right half of input word maps into a numbered bit position one bit higher in order to accommodate out(17) which is set to a logical one to indicate that there was no violations of the coding constraints in the input word.
In order to analyze the thirty two bit input word and insure that the even and odd interleaves satisfy the coding constraints, the input word needs to be further subdivided into IN={intLO, intLE, intRO, intRE} where intLO={in(1), in(3), in(5), . . . in(15)}, intLE={in(2), in(4), in(6), . . . in(16)}, intRO={in(17), in(19), in(21), . . . in(31)}, and intRE={in(18), in(20), in(22), . . . in(32)}. Each of these interleaves is eight bits long. A table of xe2x80x9cbadxe2x80x9d eight bit words, such as Table A in FIG. 2, is established to compare against the eight bit interleaves. The eight bit words in Table A are sometimes called xe2x80x9cviolationsxe2x80x9d, and Table A was established to facilitate analysis, minimize global constraints, minimize interleave constraints and eliminate low Hamming weights. Table A is used as a pointer to a four bit replacement, shown in Table B in FIG. 2, for the interleave that is in violation of the coding constraints.
When either right interleave, intRO and intRE, is found to be identical to one of the eight bit words in Table A, the corresponding four bit word in Table B is selected, reversed and substituted for the interleave in violation. For instance, if the violation is 10000011, the last one in Table B, the replacement code is 1101 which is the reverse of the last code in Table B. If the violation is in intLO or intLE, then intLO or intLE are reversed, compared to Table A to select the replacement four bit code. For example, if intLO=11000001, the reverse is 10000011 which selects 1011 from Table B.
The coded output word from the encoder can be represented as OUT={out(1), out(2), out(3), . . . out(32), out(33), out(34)}, where out(34) is the added parity bit after coding is finisher. Once a violation is detected the middle bit position in the coded output word is set to out(17)=0 which becomes the overall violation indicator. If the left half of the input word IN has a violation, out(16)=1, and for a right half violation, out(18)=1. If there is an odd interleave violation, out(14)=1, for the left half of the input word, and out(20)=1 for a violation for the right half of the input word. When there is an even interleave that is in violation, out(12)=1 for a violation in the left half and out(22)=1 for a violation in the right half. Each of the flag bits out(12), out(14), out(16), out(18), and out(20) are a logical xe2x80x9c0xe2x80x9d if there is not a violation. If only on interleave in the left half is in violation, the selected four bit code word from Table B is inserted into outLE(2, 4, 6, 8) and the valid interleave, either intLE or intLO, is copied from the input word to OUT{LHO}=out(1), out(3), . . . out(15), where OUT{LHO} is the odd interleave in the left half of the output word. When the left half violation flags are both set to out(14)=1 and out(12)=1, both interleaves are replaced by a four bit violation code from Table B in the first four positions in both interleaves, leaving out(9), out(11), out(13) and out(15) unused and each filled with a logical one. When there is no violation, out(17)=1, out(18)=in(17), but when a violation is detected, out(17)=0, bit position out(18) is used to indicate whether the violation is in the right half; therefore, bit position out(10) is used to contain in(17) when out(17) indicates a violation and the right half of the output code word does not have a violation out(18)=0.
If the right half of the input word has a violation, the right half violation indicator, out(18)=1, out(20)=1 for a violation in the odd interleave of the right half of the input word, and out(22)=1 for a violation in the even interleave of the right half of the input word. If only one interleave in the right half is in violation, the selected four bit code word from Table B is reversed and inserted into outRE(26, 28, 30, 32) and the valid interleave, iether intLE or intLO, is copied from the input word to OUT{RHO}=out(19), out(21), . . . out(33), where OUT{RHO} is the odd interleave in the right half of the output word. When he left half violation flags are set to out(20)=1 and out(22)=1, both interleaves are replaced by a reversed four bit violation code from TABLE B in the last four positions in both interleaves, leaving out(19), out(21), out(23) and out(25) unused and each filled with a logical one. When there is no violation, out(17)=1, out(16)=in(16), but when a violation is detected, out(17)=0, bit position out(16) is used to indicate whether the violation is in the left half; therefore, bit position out(24) is used to contain in(16) when out(17) indicates a violation and the left half of the output code word does not have a violation out(16)=0.
There is additional encoding steps that might be required in some cases. This step is sometimes needed to eliminate long runs of consecutive zeros at either end of a codeword. The goal is to have at most 5 consecutive zeros at either end. This way, when codewords are concatenated and a parity bit is inserted, there are most 11 consecutive zeros. After main encoding steps are completed, it is determined which of the following four statements is true for the codeword out(1:33): (1) there are not 6 consecutive zeros at either the left or the right end of the codeword; (2) there are 6 consecutive zeros at the left end of the codeword; (3) there are 6 consecutive zeros at the right end of the codeword; and (4) there are 6 consecutive zeros at both the left end and the right end of the codeword.
For most of codewords, only statement (1) is true. In this case, the word out(1:33) is sent unchanged to the output of the encoder. If statement(2) is true, the codeword out(1:33) is mapped to codeword out2(1:33) according to the following rules: out2(15:20)=(1 0 0 0 0 1); out2(1:14)=out(7:20); and out2(21:33). In other words, a portion of the codeword is shifted 6 positions to the left which puts the bits 100001 in the middle. These six bits are referred to as a xe2x80x9cshift signaturexe2x80x9d. It should be noted that codeword out(1:33) can not have xe2x80x9c000xe2x80x9d in positions out(16), out(17), out(18) because this would indicated that there was a violation in the codeword, (out(17)=0), but there was no violation in the left half, (out(16)=0), and there was no violation in the right half, (out(18)=0). Therefore the xe2x80x9cshift signaturexe2x80x9d can indicate during the decode process that the shift had occurred.
If statement (3) is true, then the codeword out(1:33) is mapped to codeword out2(1:33) according to the following rules: out2(15:20)=(1 0 0 0 1 1); out2(1:14)=out(1:14); and out2(21:33)=out(15:27). If statement (4) is true, then the codeword out(1:33) is mapped to codeword out2(1:33) according to the following rules: out2(15:20)=(1 0 0 0 1 0); out2(1:14)=out(7:20); out2(21:26)=(1 1 1 1 1 1); and out2(27:33)=out(21:27).
A decoder is designed and constructed to perform the inverse of the steps of the encoder in order to recreate in(1:32) from out(1:33). The first step for the decoder is to determine whether any post processing of out(1:33) was done to create out2(1:33) and to eliminate any long consecutive zero sequences at the beginning or end of the codeword out(1:33). By looking at bit positions 16, 17 and 18 it is easy to determine that the post processing was done when all three bit positions contain a zero. If all three bit positions contain a zero, then the output codeword is out2(1:33) which created by processing out(1:33) to eliminate any long sequences of zeros at the ends of the codeword. By locking at out2(15:20), the information needed to recreate out(1:33) is obtained. A logical zero in positions 16, 17 and 18 is only possible if there was post processing since out(17)=0 indicates a code violation, but out(16)=0 indicates no violation in the left half, and out(18)=0 indicates no violation in the right half.
Once out(1:33) is determined, then looking at out(17) indicates if any further manipulation of the data is required. If out(17)=1, there are no codeword violations and in(32)=out(1:16), out(18:33). If out(17)=0, then there were RLL codeword violations that were corrected and a reverse of the encoding steps must be done to recreate in(1:32). A violation in the left half the original input word is indicated by out(16)=1, and out(18)=1 will indicate that a right half violation of the RLL coding rules. A left half odd interleave violation is indicated by out(14)=1 and an even interleave violation in the original input signal, in(1:32), is indicated by out(12)=1. If the right half of the original input signal in(1:32) does not have any codeword violations then out(10) will contain in(17). A right half odd interleave violation in the original in(1:32) will be indicated by out(20)=1, and an even interleave violation will be indicated by out(22)=1. If there was no left half violation in in(1:32) then out(24) will contain in(16). By looking at the indicators in out(12), out(14), out(16), out(17), out(18), out(20), out(22) and the coded 8 bit word, the original input signal in(1:32) can be recreated from the output codeword out(1:33) by reversing the steps by which the output codeword out(1:33) was created.